This invention relates to computer and networking architectures and systems, including packet switching systems, routers, computers and other devices; and more particularly, the invention relates to distributed resequencing and reassembly of subdivided packets using multiple resequencing and reassembly components.
The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology.
Consumers and designers of these systems typically desire high reliability and increased performance at a reasonable price. A commonly used technique for helping to achieve these goals is for these systems to provide multiple paths between a source and a destination. Packets of information are then dynamically routed and distributed among these multiple paths. It is typically more cost-effective and technically feasible to provide multiple slower rate links or switching paths, than to provide a single higher rate path. Such designs also achieve other desired performance characteristics.
When packets from a single stream are sent through such a packet switching system, they may arrive out of order at their destinations, such as an output port of a packet switching system. In this situation, the packets must be re-ordered. Similarly, when a packet is decomposed into multiple packets which are sent to a destination, the packet must be reassembled. In some systems, one or both resequencing and/or reassembly of packets might be required. The increasing rates of traffic to be sent through a packet switching system and the corresponding number of packets which must be resequenced and/or reassembled is resulting in higher demands on the resequencing and reassembly processes. In other words, the resequencing and/or reassembly processes must be performed at corresponding higher rates. However, it is not always possible for traditional methods and mechanisms to operate at these higher rates. For example, a traditional resequencing and/or reassembly mechanism might be limited by the bandwidth of memory used in the resequencing and/or reassembly processes. New methods and apparatus are needed to resequence and/or reassemble packets, including, but not limited to those systems that can operate more efficiently and/or at fast operating rates.
A system is disclosed for resequencing and reassembling of a stream of packets. One embodiment includes multiple distributed resequencing and reassembly components. Each of the multiple distributed resequencing and reassembly components include one or more data structures for maintaining an indication of packets of the stream of packets that are stored in other distributed resequencing and reassembly components. Each of the plurality of distributed resequencing and reassembly components includes a resequencing mechanism for resequencing a subset of the stream of packets received by said each of the plurality of distributed resequencing and reassembly components. A communications mechanism is coupled to the distributed resequencing and reassembly components to allow communication among them. One or more packet merging mechanisms are coupled to the distributed resequencing and reassembly components to receive packets of the stream of packets to produce a resequenced and reassembled stream of the stream of packets.